package lib

import "algorithms/ds"

func init() {
	Probs = append(Probs, Problem{
		Num:         95,
		Discription: "生成节点值为1-n的所有不通风二叉搜索树",
		Level:       2,
		Labels: map[string]int{
			"回溯":    1,
			"二叉树":   1,
			"二叉搜索树": 1,
		},
	})
}

//一路递归往下，然后回溯往上
//思路：遍历根节点可能的取值，从而确定左孩子和右孩子的取值范围，递归返回左孩子和右孩子所有可行的组合，再遍历左孩子和右孩子的取值，构成根节点的组合
func GenerateTrees(n int) []*ds.TreeNode {
	var travel func(int, int) []*ds.TreeNode
	travel = func(start int, end int) []*ds.TreeNode {
		if start > end {
			return []*ds.TreeNode{nil}
		}

		allNodes := make([]*ds.TreeNode, 0)
		for i := start; i <= end; i++ {
			//移动区间，不断地递归减少搜索空间
			leftAllNodes := travel(start, i-1)
			rightAllNodes := travel(i+1, end)

			//根据所有左子树和右子树的组合组成不同节点
			for _, left := range leftAllNodes {
				for _, right := range rightAllNodes {
					root := &ds.TreeNode{
						Val:   i,
						Left:  left,
						Right: right,
					}
					allNodes = append(allNodes, root)
				}
			}
		}

		return allNodes
	}

	return travel(1, n)
}
